Суме сегмената променљивог низа

Овај задатак је поновљен у циљу увежбавања различитих техника решавања.

Напиши програм који израчунава збирове датих сегмената низа (поднизова узастопних елемената), при чему се током рада програма поједини елементи низа могу мењати.

Улаз

У првој линији стандардног улаза налази се број \(n\) (\(1 \leq n \leq 100000\)), а у наредној линији низ од \(n\) елемената (елементи су цели бројеви између 0 и 10, раздвојени са по једним размаком). У наредној линији налази се број \(m\) (\(1 \leq m \leq 100000\)), а у наредних \(m\) линија упити. Подржане су две врсте упита:

• p \(i\) \(v\) – извршавање овог упита подразумева да се у низ на позицију \(i\) упише вредност \(v\) (\(0 \leq i < n\), \(0 \leq v \leq 10\)).
• z \(a\) \(b\) – извршавање овог упита подразумева да се израчуна и на стандардни излаз испише збир елемената низа који су на позицијама \([a, b]\).

Излаз

Стандардни излаз садржи резултате z упита (сваки у посебној линији).

Пример

Улаз

5
1 2 3 4 5
5
z 0 4
z 2 3
p 2 5
p 3 6
z 0 4

Излаз

15
7
19